class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        // 1、初始化
        int n = nums.size();
        vector< vector<int> > ret;
        // 2、排序
        sort(nums.begin(), nums.end());
        // 3、依次固定一个数，然后使用“三数之和”解决问题
        for(int i = 0; i < n - 3;) 
        {
            // 4、再依次固定一个数，然后使用“双指针”解决问题
            for(int j = i + 1; j < n - 2;) 
            {
                int left = j + 1, right = n - 1;
                double aim = (double)target - nums[i] - nums[j];
                // 5、双指针算法找到两数之和等于 aim 的元素
                while(left < right)
                {
                    double sum = nums[left] + nums[right];
                    if(sum < aim) ++left;
                    else if(sum > aim) --right;
                    else
                    {
                        ret.push_back( {nums[i], nums[j], nums[left], nums[right]} );
                        ++left, --right; // 保证 left、right 选择的元素不漏
                        // 对 left、right 已经选择过的元素去重
                        while(left < right && nums[left] == nums[left - 1]) ++left;
                        while(left < right && nums[right] == nums[right + 1]) --right;
                    }
                }
                // 保证 j 选择的元素不漏
                ++j;
                // 对 j 已经选择过的元素去重
                while(j < n - 2 && nums[j] == nums[j - 1]) ++j;
            }
            // 保证 i 选择的元素不漏
            ++i;
            // 对 i 已经选择过的元素去重
            while(i < n - 3 && nums[i] == nums[i - 1]) ++i;
        }
        // 6、返回最终结果
        return ret;
    }
};
/*
- 时间复杂度：O(n^3)
- 空间复杂度：O(1)
*/
